package algorithms.leaning.class21;

import common.util.MyUtil;

/**
 * arr是面值数组，其中的值都是正数且没有重复。再给定一个正数aim。
 * 每个值都认为是一种面值，且认为张数是无限的。
 * 返回组成aim的方法数
 * 例如：arr = {1,2}，aim = 4
 * 方法如下：1+1+1+1、1+1+2、2+2
 * 一共就3种方法，所以返回3
 *
 * @author guichang
 * @date 2021/6/22
 */

@SuppressWarnings("all")
public class Code3_动态规划_货币组成_无限张 {

    public static void main(String[] args) {
        int[] arr = {5, 10, 20, 50, 100};
        int aim = 105;
        MyUtil.print(ways(arr, aim));
        MyUtil.print(waysDp(arr, aim));
        MyUtil.print(waysDp2(arr, aim));
    }

    public static int ways(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        return process(arr, 0, aim);
    }

    private static int process(int[] arr, int index, int rest) {
        if (index == arr.length) {
            // rest为0的话算一张
            return rest == 0 ? 1 : 0;
        }
        int ways = 0;
        for (int i = 0; arr[index] * i <= rest; i++) {
            ways += process(arr, index + 1, rest - arr[index] * i);
        }
        return ways;
    }

    public static int waysDp(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];
        dp[N][0] = 1;
        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest <= aim; rest++) {
                int ways = 0;
                for (int i = 0; arr[index] * i <= rest; i++) {
                    ways += process(arr, index + 1, rest - arr[index] * i);
                }
                dp[index][rest] = ways;
            }
        }
        return dp[0][aim];
    }

    public static int waysDp2(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];
        dp[N][0] = 1;
        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest <= aim; rest++) {
                dp[index][rest] = dp[index + 1][rest];
                if (rest - arr[index] >= 0) {
                    dp[index][rest] += dp[index][rest - arr[index]];
                }
            }
        }
        return dp[0][aim];
    }

}